package top.whk0710.swordoffer._1TwoDimArray;

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.SQLException;

/**
 * 牛客网剑指offer第一题：二维数组中的查找
 * 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
 * 每一列都按照从上到下递增的顺序排序。
 * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * */
public class Solution {

	public static void main(String[] args) throws SQLException{
		int[][] abc = {{1,2,3,4},
				       {1,2,3,4},
				       {1,2,3,4}};
		System.out.println(abc.length);//行数
		System.out.println(abc[0].length);//列数
	}
	/**
	 * 简单暴力的解法，时间复杂度为n*m
	 * 直接遍历全二维数组
	 * */
	public boolean Find(int target, int [][] array) {
		if(array.length <= 0) return false;
		int row = array.length;
		int col = array[0].length;
		for(int i=0;i<row;i++){
			for(int j=0;j<col;j++){
				if(target==array[i][j])
					return true;
			}
		}
		return false;
    }
	/**
	 * 二分查找，因为是有序数组
	 * 行为基准，列来进行二分查找
	 * 这样的时间复杂度为O(NlogM)
	 * N为行数，M为列数
	 * */
	public boolean Find2(int target,int [][] array){
		if(array.length <= 0) return false;
		//以行为基准吧
		for(int i=0;i<array.length;i++){
			int low = 0;
			int high = array[0].length - 1;
			
			while(low <= high){
				int mid = (low + high) >>> 1;
				if(target == array[i][mid]){
					return true;
				}else if(target < array[i][mid]){
					high = mid - 1;
				}else{
					low = mid + 1;
				}
			}
		}
		return false;
	}
	/**
	 * 行列同时查找，因为都有序
	 * 时间复杂度为O(M+N)
	 * https://www.nowcoder.com/questionTerminal/abc3fe2ce8e146608e868a70efebf62e
	 * 跟右上角，大于就让行下移动(row++)，小于就让列左移(col--)
	 * */
	public boolean Find3(int target,int[][] array){
		int row = 0;
		int col = array[0].length - 1;

		while (row <= array.length - 1 && col >= 0) {
			if (target == array[row][col])
				return true;
			else if (target > array[row][col])
				row++;
			else
				col--;
		}
		
		return false;
	}
}
